This invention relates generally to a method and system for mapping traffic congestion and in particular to a method for improving the accuracy of said mapping when a relatively small percentage of vehicles are used as traffic probes. In particular, this method provided also for using existing radio networks such as Public Land Mobile Networks (PLMN) and land mobile Private/Public Data Networks (PDN).
Traffic congestion is an increasingly serious problem in cities.
One way to identify and map such congestion in real time (the first step to relieving it) is to identify and map the positions of vehicles that are stopped or moving slowly. Such systems are often referred to traffic control and car navigation in the field of Intelligent Transport Systems (ITS).
PCT publication WO 96/14586, published May 17, 1996, the disclosure of which is incorporated herein by reference, describes, inter alia, a system for mapping of vehicles in congestion.
In one embodiment described in the above publication, a central station broadcasts a call to the vehicles which requests tho se vehicles which are stopped or which have an average velocity below a given value to broadcast a signal indicative of their position. Such signals are broadcast in slots, each of which represent one bit (yes or no) which relates to a position. Preferably, only one logical slot (that may be represented by more than one actual slot) is used to define the related position. Such signals are then used to generate a map of those regions for which traffic is delayed or otherwise moving slowly.
Preferably, an additional call is sent to the vehicles requesting transmission of indication signals which locate the slow moving or delayed vehicles at a higher resolution than that of the first call. Further calls may be made to allow for transmission of additional information on the status of the vehicles and/or to provide further characterization of the delays.
FIG. 1 shows an initial map generated by such a method, wherein the area represented by a pixel (slot) may, for example, be of the order of 250 to 1000 meters square. In a preferred embodiment of the invention described, the system then determines, based, inter alia, on the extent of the various contiguous areas which shows positive responses, a smaller area or areas for further study. Preferably, the system broadcasts a further query requesting those vehicles within the smaller area that have at least a given delay (which may be the same as or different from that used in the first query) to broadcast in slots, each representing a position, using a finer resolution, for example, 100 to 250 meters square. Based on the responses to this query a second map such as that shown in FIG. 2 is generated. As can be seen from FIG. 2, various branches of a road network radiating from an intersection, designated as A-F in FIG. 2, can be identified. To improve the usefulness of the display, a background map, such as a road map, may be displayed underlying the displays of any of FIGS. 1, 2 or 4 (described infra).
In the event that additional information relating to the delay is desired, further queries can be made. For example, vehicles which are traveling toward the intersection can be requested to broadcast in a slot which corresponds to the slot they are in and to their velocity toward the intersection. This allows for generation of the graph shown in the lower portion of FIG. 3. Additional slots may be used for the acquisition of other information regarding the responding vehicles. Such information may also be graphed as shown in the upper portion of FIG. 3.
Alternatively or additionally, a map which shows the average velocity of the vehicles toward the intersection as a function of the position can be generated. Such a map is shown in FIG. 4. To acquire the information needed for generating such a map, a number of queries may be made, each requesting an indication from all vehicles within the area of interest having a given average velocity toward the intersection. The responding vehicles would broadcast their indication signals in slots corresponding to their position. In the map of FIG. 4, the velocity for a given pixel is determined, for example, as the average velocity of the reporting slots for that position. In a display of the map of FIG. 4, the velocity or delay toward the intersection can, for example, be displayed as a gray scale value or as a color, with for example red being the highest velocity or delay and blue being a minimum displayed velocity or delay.
FIG. 5 is a generalized block diagram for a system useful for performing the ITS function described above (and which is also useful for the method of the present invention). FIG. 5 shows a base station or control center 91 having a control center transmitter 79 which broadcasts queries and optionally other signals to vehicles on command from a control computer 80. A remote vehicle 85 (only one vehicle is shown for simplicity) receives the query at a vehicle receiver 84 and transmits commands to a microprocessor 86, based on the queries it receives from the control center.
Microprocessor 86 also receives information regarding the status of the vehicle from one or more information generators and sensors indicated by reference numeral 88. This information may be sent by the sensors on a regular basis or may be sent on command from the microprocessor.
Microprocessor 86 is then operative to command vehicle transmitter 90 to transmit indication signals (or if required, information bearing signals) in a suitable slot in accordance with the information received by microprocessor 86.
The indication (or other) signals are received by a control center receiver 92 and processed by receiver 92 and computer 80. While the operation and construction of the apparatus designated by reference numerals 82, 84, 86 and 90 is straightforward and needs no further explanation, the operation of receiver 92 is usefully expanded upon with reference to FIG. 6.
Generally speaking, the RF signals transmitted by the vehicle may be at any frequency slot. It is to be expected that there will a certain amount of frequency diversity caused by the imperfect accuracy and stability of the vehicle transmitters 90. The slots are wide enough to accommodate this diversity.
Furthermore, often the system utilizes very large numbers of vehicles. If too many of these vehicles (in some particular situation) transmit in the same slot, then the total power transmitted may exceed authorized ERP or dynamic range restrictions. To overcome this problem longer, lower power, pulses may be used for indication signals. Furthermore, if a single receiver is used for receiving signals for all of the slots, intermodulation effects may cause spurious signals to appear in slots for which no actual signals have been received.
These problems as well as near-end to far-end transmission problems are substantially solved by the system shown in FIG. 6 and by certain constraints placed on the system which are not shown in FIG. 6. The problems and constraints but are described in the above referenced PCT publication, which should be consulted for a more complete exposition of the method and apparatus shown in FIGS. 1-6.
FIG. 6 shows a receiver system corresponding generally to reference number 92 and to a portion of computer 80 of FIG. 5. While the system of FIG. 6 is suitable for the prior art ITS system of the PCT publication, it is also suitable for use with the ITS system of the present invention.
An antenna 94 (or an array of antennas) receives signals from a plurality of vehicles simultaneously and passes them to a receiver and (optionally) AGC 96. Receiver and AGC 96, which may be of conventional design, down converts the received signals from RF to IF frequencies. The threshold levels of the detection process may be dependent on the AGC process. Alternatively, the system is operated in a closed loop mode in which the power radiated by the vehicles is dependent on the power received by the base station.
The IF signal is digitized by an A/D system 98 and further down converted by a down converter 100 to base band. It should be understood that this receiver/down converter system does not demodulate the incoming signals, but only down converts the RF so that the same relative frequency differences of the signals is present at the output of converter 100 as in the incoming signals, except that the absolute frequency has been reduced to a low frequency from the RF frequency of the transmitted signal. At these lower frequencies digital systems can be used to analyze and detect the signals.
The low frequency band signals are fed to a series of correlation filters 102 (correlation-type receiver), each of which has a very narrow bandwidth which is related to the correlation time of the correlation filter. Preferably, the frequency bandwidths of adjacent receivers 102 overlap so that the entire bandwidth of each of the slots is covered by one set of receivers 102. The output of each of the receivers is compared to a threshold 104 to determine if a signal is present at the frequency of the respective receiver 102 and the outputs of all of threshold detectors for a given slot are OR gated (or the best signal is selected) to determine if any signal is present in the slot.
In an alternative preferred embodiment of the embodiment disclosed, the strongest output of the set of correlation receivers is chosen for comparison with a threshold, with or without post-detection integration.
Use of a plurality of overlapping narrow band receivers in this manner also reduces the extent of side lobes of the detection process outside the band of the slot. This allows for closer frequency spacing of the slots since interference between slots having adjacent frequencies is reduced.
One set of receivers 102, threshold detectors 104 and an OR gate is provided for each slot and is referred to herein as a slot detector unit. Slot detector units for all of the slots feed a data processor 108 which, together with computer 80 processes the data as described above. When large numbers of vehicles are used in the system and intermodulation becomes a problem (or if AGC is used, and low level signals are lost), it may be necessary to provide a plurality of front end portions of receiver 92 (the front end being defined as receiver 96, converter 98 and converter 100), where each front end receives signals from only a portion of the entire frequency band including one or many of the slots. The function of correlation receivers 102 may also be implemented, for example, using set of DFT""s or an FFT (for CW signals), matched filters or other correlation receiver methods or other optimum receiver methods, depending on the transmitted signals. Other methods such as energy detectors (e.g., radiometers) with or without tracking may also be used, however, they will give less optimal results, because of practical limitations on input band-pass filter designs.
It should be understood that using a plurality of correlation receivers for the same slot may increase the false alarm probability and hence the threshold for positive detection may be adjusted to provide a desired low false alarm probability.
The system may also be provided with a display 110 for displaying the data, and with a user interface 112 which is used by an operator to control both the operation of the system. The user interface also preferably controls the display and the memory to allow for the operator to review the maps previously generated or to generate new displays based on information previously received.
This system works well. However, there is a need for improved accuracy of mapping and/or utilizing a relatively small percentage of participating vehicles.
The present invention provides a system and method for mapping parameters of traffic congestion, e.g., road congestion, relative to a focus. Mapping of the road congestion may include determination of an average length of the road congestion over a time interval, motion rate in the road congestion and arrival rate to the road congestion. These parameters, in turn, may be used to determine an expected delay in traveling throughout the road congestion as well as trends (i.e., changes with time) in the road congestion.
The mapping is performed relative to a mapping focus, typically the front end of a road congestion. The mapping focus is preferably identified using the system and method described in the above-mentioned PCT Publication WO 96/14586, or it may be identified using any other suitable method known in the art, for example, by simple polling of predesignated target vehicles. Alternatively, the mapping focus may be provided from an external source, for example, based on reports regarding a problematic intersection or suspect intersections that are to be continuously monitored.
In an embodiment of the present invention, the mapping system constructs snapshots of mapping samples received from a small percentage of predesignated probes, e.g., a small percentage of vehicles equipped with an appropriate receiver and transmitter. The mapping samples are preferably received in response to predefined broadcast queries sent from the mapping system. In an embodiment of the invention, the determination of the average length of a road congestion may be based on a direct approach, obviating the need to estimate discrete lengths of the road congestion, in dynamic conditions that may include variations in the arrival rate of vehicles to the road congestion and the departure rate of vehicles from the congestion over time.
In preferred embodiments of the invention, the average motion rate within the road congestion may be determined without the need to increase the bandwidth of the radio spectrum that is used by the probe vehicles. The determination of motion rate in addition to the length of the congestion enables to estimate the expected time delay for a vehicle that is about to enter the road congestion. The method of determining motion rate may isolate reporter vehicles, whereby of reporting may be utilized to improve the method of the invention, e.g., to increase the accuracy at which the length of the road congestion may be determined and/or to provide information about trends in the road congestion, i.e., expansion or contraction of the congestion. Such isolated mapping enables the system, for example, to concatenate non-overlapping segments in the mapping samples and, thereby, to estimate the average arrival rate to the congested road. This technique may be used in conjunction with an estimated departure rate to provide trends in the average length over time, whereby a preferred path chosen by a vehicle may be selected based on a current time delay as well as on the trend in the road congestion.
The concatenation of non-overlapping segments of mapping samples, in accordance with a preferred embodiment of the invention, may also be useful for estimating the percentage probe vehicles within the road congestion. Based on this estimation, in conjunction with a calculation of the estimated arrival rate and the estimated motion rate, the average length may be determined more accurately. This means that the number of mapping samples can be optimized to provide an accurate determination of the average length of the road congestion based on the parameters described above. Pre-stored data which may be generated by computer simulation of different road congestion conditions may be used in determining the optimum number of mapping samples for average length determination.
In accordance with the present invention, as described herein, concatenated mapping samples may be used to estimate the arrival rate and the percentage of probes. In traffic situations where two or more road congestions are correlated, several such concatenations from several different road congestion may be combined to improve parameter estimation. For example, to estimate the percentage of probes based on Maximum Likelihood estimator for Binomial distribution, the concatenation of more than one concatenated mapping samples from several correlated roads may be used by a statistical estimator. This can be used to improve estimates from short concatenated sample at an early stage of mapping a road congestion.
The motion rate within the road congestion, which may be detected based on two mapping samples, may also be used for determining a minimum required rate for taking snapshots of mapping samples according to a desired accuracy in determining the average congestion length. In embodiments of the present invention, the level of accuracy in determining average length based on motion rate may be estimated by computer simulation and provided as pre-stored data to determine an appropriate mapping sample rate. As mentioned above, motion rate can be detected by two mapping samples. At an initial stage of a mapping process, when the average arrival rate of vehicles to the road congestion and the probability of an arriving vehicle being a probe cannot be correctly calculated, prior statistical data may be used to initiate the estimation process. Refinement of these initial values may be performed during the sampling process by constructing concatenated segments of non-overlapping mapping sample segments and determining the average arrival rate as well as the percentage of probes, thereby enabling to determine the probability of an arriving vehicle being a probe. A similar approach may be used for determining the number of mapping samples according to the pre-stored data.
The pre-stored data may be based on computer simulation to provide minimum error in the determination of the average length or a modified average length. The modified average length may take into account predetermined parameters, e.g., giving more weight to later mapping samples than to earlier mapping samples or any other desired criteria that may result in a more accurate estimation process. As traffic condition are being mapped, statistical data is collected relating to average arrival rates and distribution of probe vehicles, whereby the system converges to realistic values at relatively early stages of the mapping, even before one would expect to have sufficient mapping samples to estimate these parameters.
In case of traffic light control, the sampling rate may be adjusted in accordance with the rate of change of the traffic lights, e.g., the timing of the green light activations. The timing of light changes may be provided by probe reports according to their reaction time to green light setting calibrated to distance from the traffic light. According to this embodiment, the times may be provided by a report from a probe which has been isolated for the purpose of motion rate estimation and other estimations, as described above. It should be noted that the average road congestion length may be determined with minimal error when the departure rate in each mapping sample is substantially equivalent to the average arrival rate.
When the average departure rate is not equal to the average arrival rate, the departure rate may be artificially adjusted to increase or decrease the length of the mapping samples, thereby to adapt the average departure rate to the average arrival rate. This may assist in determining the length of road congestion. Once the road congestion length is determined, based on the artificial adjustment, a readjustment stage may be applied to compensate for the artificial adjustment. The compensation may be based on a new weighted average which takes into account a trend in the length of road congestion. At any given time, the average length determination may be based on the latest mapping samples according to the number of mapping samples that will best determine the average length of the road congestion. Successive average length values may fed through an appropriate filter, as is know in the art, to remove large, random changes in value.
The present invention is comprised in a number of improvements on the prior art system which improve the position-related accuracy of the system.
As in the prior art system described above, preferred embodiments of the present invention may utilize the position related data transmission system of the above referenced PCT publication. In addition, the present invention may utilize the general structure of the transmitter and receiver as described in that publication and in the Background of the present invention. It should be noted that, because the present invention may utilize a communication platform and related technology similar to those described in the above mentioned publications, many features of the methods, devices and systems described in that publication are also applicable to the present invention.
According to some aspects of some preferred embodiments of the invention, mapping of congestion is based on identification of the starting point of traffic congestion and a determination of a distance of vehicles from a congestion start point or focus. The length of the congestion is estimated from the distance of the vehicle farthest from the congestion whose velocity is below a given velocity, preferably for some minimal time period.
Preferably, the vehicle positions are not determined for individual vehicles. Rather the vehicle report according to their positions, that correspond to a pre-determined sub-area, if they are stopped or if their velocity is below some value.
Preferably, vehicle positions over a time period are combined to form a congestion map.
Preferably, the positions that are combined are determined at the same position resolution. Alternatively, they do not.
According to an aspect of some preferred embodiment of the invention, the position of a vehicle is reported based on a distance to a known focus of a congestion.
In a preferred embodiment of the invention, the location of a potential congestion is determined by vehicles that are stopped or moving slowly reporting their positions at a low resolution, for example using a rectangular grid for two dimensional mapping. Once a potential congestion is identified, the position of the vehicles is reported based on their distance from a focus of congestion.
There is thus provided, in accordance with a preferred embodiment of the invention, a method of estimating the position, in an ITS system, of the length of congestion at a focus of a slowdown, the method comprising:
determining the positions of one or more vehicles farthest from the focus as a function of time; and
estimating the length of the congestion based on the function.
Preferably, the position is estimated as the position of a vehicle farthest from the focus.
Preferably, the position is estimated as the position of a vehicle furthest from the focus during a given preceding time period.
There is further provided, in accordance with a preferred embodiment of the invention a method of improving the reliability of an ITS system, comprising:
determining the position of a plurality of vehicles;
determining an indication of a traffic stoppage if more than one vehicle is stopped along line of vehicles.
Throughout this disclosure, where applicable, the terms and phrases listed below may be defined as follows:
Mapping Focus
A position in a mapped road that defines the front end of the mapping range towards traffic moves usually refers to the front end of a road congestion.
Probe
A vehicle equipped with a transmitter connected to a computer both comprising an intelligent transmitter wherein the computer is provided with timing and positioning peripherals that according to a predetermined procedure can identify congested conditions and motion cycles parameters in a congested road, preferably equipped also with a receiver that enables a mapping system to control the activity of the reports preferably including levels of congestion to be experienced by the probe fore a report, resolution of position report, actual report time of a characteristic value of its position, disabling transmission of probes that are closer than a certain position to the mapping focus and re-enabling the transmission, and according to a predetermined protocol reports will preferably include, but not limited to, one or more of the following: arrival time to a congested road preferably in a short form such as elapsed time within a mapping cycle, indication on out of mapping range, time related to passing a position such as mapping focus, expected time of green light turn on when a road controlled by traffic light based on predetermined estimate for the delay in response of vehicle to departure according to its position in a waiting line preferably in a short form such as elapsed time within a cycle such as cycle of mapping samples or cycle of traffic light control (several of such different reports can be averaged by the mapping system); reports will preferably use a method of transmission that reports characteristic values by transmitting a signal in slot that best represents its characteristic value.
Characteristic Value of Position
A value that a probe provides according to a predetermined protocol regarding its position, or an indication on its position, such as its distance from a mapping focus along a road or otherwise along a path determined by the protocol.
Mapping System
A system comprising a receiver that receives reports from probes and a computer that constructs mapping samples from received reports and processes the mapping samples to provide characteristics of the road congestion including, but not limited to, one or more of the following reports: departure length from the road congestion between mapping samples and preferably its varying characteristics; arrival length to the congested road between mapping samples and preferably its varying characteristics; estimated length of road congestion; estimated average waiting time in a congested road; trend in the length of the congested road; estimated length of a congested road at a certain time and possibly interpreted values of length in a congested road to number of vehicles based on expected average occupation length of a vehicle such as in a stoppage.
The system will preferably be equipped also with a transmitter that according to a predetermined protocol controls the transmission of probes preferably including, but not limited to, one or more of the following: required criteria of traffic conditions that enables a report; resolution of reports; and preferably the time of the transmission of a characteristic value of a position that relates to earlier time than the transmitted time, disabling transmission of probes that are closer than a certain position to the mapping focus and re-enabling the transmission.
The system will preferably allocate slots to the probes that according to a predetermined protocol slots divide a range of positions or time interval to smaller segments so that each range will be represented by a different slot.
Mapping Sample
One or more time correlated characteristic values of position usually relates to time constraints that provide a snapshot of probe positions in a congested road.
Range Characteristic Value
A value that represents one or more characteristic values such as positions within a range of reports in a mapping sample. Range characteristic values can provide an average of positions or average distance from the mapping focus or a weighting average that consider parameters that affect inaccuracy in reports. Range characteristic value can also average several reported values about a common estimate made by probes, for example, estimate of green light time setting reported by more than one probe in a waiting line according to distance form the traffic light and reaction time to the traffic light. Such reports can use differential updates referred to a common time reference.
Occupation Length of Vehicle
Average segment along a road equivalent to the length between front of one vehicle in front or behind of it.
Mapping Range
A range respective with the mapped part of the road usually covers the congestion starting from the mapping focus.
Using the above terminology, in according with preferred embodiments of the invention, there is thus provided a method of estimating the length of a road congestion, based on probe vehicles reporting characteristic values of their position to a receiver of a mapping system which processes the reports, the method including:
(a) constructing a predetermined number of mapping samples,
(b) determining in each mapping sample a position that relates to the position of a probe relatively far from a mapping focus, preferably a position close to the farthest probe position; and
(c) selecting from the positions determined in step (b) the position which is the farthest from the mapping focus, thereby to determine an indication of the length of the road congestion.
In a preferred embodiment, the position determined in step (b) is the position of the farthest probe from the mapping focus.
According to an embodiment of the invention, after construction of a mapping sample a response is transmitted to the reporters that disables transmitters that did not transmit a report within a pre-selected range in the constructed mapping sample, to prevent the disabled transmitters from continuing to report. The selected range may include the position of the farthest probe.
Additionally, in accordance with preferred embodiments of the invention, there is provided a method of determining traffic motion and length of road congestion, in a system wherein probes, in response to a predetermined protocol, report characteristic values of their position to a receiver of the mapping system which processes the reports, the method including:
(a) constructing a mapping sample that includes at least one of said reports,
(b) selecting a range of said position characteristic values in which the farthest reporter from a mapping focus is identified in a mapping sample constructed in (a),
(c) transmitting to reporters a response that according to a predetermined procedure disables transmitters that did not transmit a report within the selected range from continuing to report,
(d) receiving further reports and constructing a subsequent mapping sample,
(e) repeating steps (a) to (d) according to a predetermined procedure,
(f) selecting from the ranges selected in step (b) the farthest selected range to be indicative of the length of the road congestion; and
(g) determining motion length toward a mapping focus by calculating a range characteristic value for a range in a mapping sample, subsequent to the first mapping sample, which includes the position characteristic value indicative of the closest position to the mapping focus and calculating the difference between the said range characteristic value and the range characteristic value of a corresponding selected range in an earlier mapping sample.
In an embodiment of the present invention, the range selected in step (b) is substantially the characteristic value of position of the farthest probe.
In an embodiment of the present invention, the indication of the length of the road congestion is determined substantially based on the farthest selected position in the constructed mapping samples.
In an embodiment of the present invention, the resolution of the position reports acquired from the probes is determined according to an occupation length of vehicle in a congested road in different traffic conditions.
In an embodiment of the present invention, at least two different reports from at least one probe are required to determine length of road congestion.
In an embodiment of the present invention, the number of mapping samples is 3 to 6 for expected average percentage of probes in the range of 3 to 5 percent and wherein the time interval.
In an embodiment of the present invention, the number of mapping samples is determined based on pre-stored data relating to an average motion over time period, estimated probability of probe arrival, and estimated arrival rate of vehicles. In some embodiments of the invention, the mapping system estimates the probability of probe arrival according to a predetermined procedure based on the percentage of probes among vehicles arriving at the congestion, and the method may further include:
concatenating a plurality of non-overlapping segments of consecutive mapping samples according to motion between mapping samples,
determining the number of vehicles in the concatenated segments by the ratio of the length of the concatenated segments to expected occupation length of vehicles in the road congestion, and
determining by a statistical estimator the percentage of probes based on the distribution of the accumulated probes identified over the period relevant to mapping samples of concatenated segments.
In an embodiment of the present invention, the statistical estimator is chosen according to assumed Binomial distribution of probes in the concatenated mapping samples.
In an embodiment of the present invention, the number of concatenated mapping samples is substantially limited to elapsed time interval wherein the expected probability of probe arrival to the road congestion is stationary.
In an embodiment of the present invention, the pre-stored data is optimized to provide the number of mapping samples to produce substantially the minimum expected error in the determined indication of the length of the congestion compared to the real average length of the congestion according to the respective mapping samples.
In an embodiment of the present invention, the optimization criterion is the minimum difference between the cumulative distribution function of errors that indicates that the estimates are too long and the cumulative distribution function that indicates that the estimates are too short.
In an embodiment of the present invention, the pre-stored data is prepared based on a simulation that shows the number of mapping samples required to provide minimum expected error for various conditions of congestion including motion rate, arrival rate and percentage of probes.
In an embodiment of the present invention, at a time prior to determining the indication on the length of the road congestion, mapping samples are adjusted according to a predetermined procedure that virtually adjusts the position of the mapping focus in the mapping samples in order to remove differences between motion rate and average arrival rate.
In an embodiment of the present invention, at a time after determining indication of the length of the road congestion, the determined indication is adjusted by a value which is indicative of the prior adjustments that were made to the mapping samples in order to remove the effect of prior adjustments on the mapping samples.
In an embodiment of the present invention, successive new indications of the length of the road congestion are determined according to a procedure that include successive newest mapping samples.
In an embodiment of the present invention, a one-dimensional median filter is applied to the successive indications on length of road congestion.
In an embodiment of the present invention, time correlated mapping samples are collected according to a required resolution of the road congestion length determination, based on departure rate of vehicles from the road congestion.
In an embodiment of the present invention, the number of vehicles in a lane segment of the road congestion is determined according to estimated occupation length of vehicles.
In an embodiment of the present invention, the number of vehicles in a lane segment of road congestion is determined according to the estimated occupation length of vehicles.
Further, in accordance with a preferred embodiment of the present invention, there is provided a method of creating conditions which enable assessment of traffic motion rate toward a mapping focus in a congested road and of the road congestion length at a certain time, wherein according to a predetermined protocol probes report characteristic values of their position to a receiver of a mapping system which processes the reports, the method including:
(a) constructing a first mapping sample that includes at least one of said reports,
(b) determining a range of said position characteristic values in which at least one of said reports was identified in the first mapping sample, and
(c) transmitting to reporters a response that according to a predetermined procedure disables transmitters that did not transmit a report within the selected range of the first mapping sample from continuing to report.
In an embodiment of the present invention, the characteristic value of a position is an indication of the distance of a reporter from the mapping focus.
In an embodiment of the present invention, the mapping sample constructed by reports is transmitted to the mapping system within a response time synchronized to the mapping system and to the reporters.
In an embodiment of the present invention, a report of a position characteristic value is a signal transmitted by at least one probe in a slot of the response time that is indicative on a range of positions.
In an embodiment of the present invention, the time of the position-related reports is determined by a broadcast query to the probes.
In an embodiment of the present invention, the selected range in which reporters are not disabled includes the position of the farthest reporter from the mapping focus.
In an embodiment of the present invention, the transmitted response to disable transmitters is a message including mapping sample that according to predetermined procedure reporters disable their transmitters from continuing to report if they had not transmitted a report within a range in the mapping sample selected according to the predetermined procedure.
In an embodiment of the present invention, after disabling a transmitter, the probe enables its transmitter by predetermined procedure at a time after it passes the mapping focus.
In an embodiment of the present invention, a non-disabled reporter reports a time indication representing its arrival at the reported position.
In an embodiment of the present invention, the time indication report is a signal transmitted by reporter in a slot that is indicative of a time interval in the mapping sample time constraints.
In an embodiment of the present invention, after a disabling response the mapping system receives the new reports and constructs a second mapping sample including new reports.
In an embodiment of the present invention, a reporter from the selected range reports an indication that it is out of mapping range if it passed the mapping focus at a time prior to time constraints of the second mapping sample. Preferably, in an embodiment of the present invention, the indication of out of mapping range determines no change in motion rate.
In an embodiment of the present invention, the indication of out of mapping range is a signal transmitted in a slot that a transmission in it is indicative on such condition.
In an embodiment of the present invention, the mapping system determines length of motion toward mapping focus by calculating a range characteristic value for a range in a mapping sample subsequent to a disabling response, which includes the position characteristic value indicative of the closest position to the mapping focus and calculating the difference between the range characteristic value and the range characteristic value of the corresponding selected range in an earlier mapping sample.
In an embodiment of the present invention, the mapping system determines the departure rate from the mapping focus in a congested road in units of length of a congested road segment per unit of time according to the determined length of motion towards mapping focus.
In an embodiment of the present invention, according to motion towards mapping focus, the mapping system determines a non-occupied space expected between vehicles along the road congestion.
In an embodiment of the present invention, the determined motion length towards the mapping focus related to average occupation length of a vehicle, including its unoccupied space, determines departure rate of vehicle from the congested road.
In an embodiment of the present invention, the time at which the traffic light system changes to a green setting is substantially identified by the mapping system through reports from probes.
In an embodiment of the present invention, according to predetermined procedure, a probe reports to the mapping system a substantial time when the traffic light system changes to the green setting by a predetermined delay taken for a vehicle to react according to its position in a waiting line.
In an embodiment of the present invention, the time of light change is substantially identified based on signal transmitted in a slot representing a time interval that best characterizes the time report.
In some preferred embodiments of the present invention, according to a predetermined procedure, the mapping system estimates arrival rate to the congestion, and the method further includes:
concatenating a plurality of non-overlapping segments of consecutive mapping samples according to the two said position related reports,
determining time intervals between two time of arrival reports corresponding to two position related reports,
determining average arrival rate in terms of segment length occupied by arriving vehicles between successive mapping samples by calculating the ratio of the total length of concatenated segment, in relation to the number of concatenated mapping samples.
In an embodiment of the present invention, the number of concatenated mapping samples is substantially limited to elapsed time interval in which the average arrival rate of probes to the road congestion is expected to be stationary.
In an embodiment of the present invention, the length of motion of non-disabled reporter towards mapping focus between two consecutive mapping samples determines the point between consecutive concatenated segments.
In addition to the system described above, the System and methods for identifying congested roads and gathering mapping samples for the implementation of the method of this invention, to determine parameters of vehicle queues, especially average queue length over time period, with priority for congested roads, existing radio networks such as Public Land Mobile Networks (PLMN) and land mobile Private/Public Data Networks (PDN) may also be used.
Examples of PLMN are GSM, IS-54, IS-136,PDC, PCS-1900, IS-95, GPRS and EDGE for GSM, WCDMA, and cdma2000 and others. Examples of PDN are Mobitex, CDPD and others. Other networks could also be included under these categories since the mapping of road congestion characteristically relate to very low velocities, and hence PHS, DECT and other similar networks could also be used.
The method suggested by the above-described invention is most valuable to estimate length and other parameters of varying queues, over time periods. The implementation of the method requires a gathering process that includes the following three stages, a) to identify a congested road, b) to determine the departure position of a queue, which in turn determines a mapping focus, and c) to construct mapping samples. The mapping samples are used to determine the parameters of a varying queue. Although in the description of the method for estimating queue parameters according to the mapping samples just one implementation possibility was elaborated in detail, the gathering part of the method is not limited to the elaborated possibility only, and in this context other methods such as polling and Aloha are mentioned. The elaborated implementation possibility has the advantage of providing rapid search and mapping that enables gradual control on the resolutions of the mapping. However this gathering method is also quite unique in the way it uses pre-designated communication slots to provide information. When plurality of transmitters use the same slot at the same time, instead of rejecting a transmission that usually caused data to be undetectable, the detected energy in such slots designates some predetermined information with to allocated slots which enables collided transmission to be valid (meaningful).
Communication methods such as used with PLMN and PDN do not consider the energy detection by itself as valid data transmission. Thus to implement the method suggested in the above described invention, in the case that such networks are considered for the gathering process, modification should be considered either to the PLMN or the PDN or to the gathering process. In the case when using such networks, as with the case of the elaborated method, the gathering process would include three stages of implementation as are used with the system suggested above. The first stage deals with the identification of congested road, preferably based on a search process that uses queries and position related responses related to a road map. The second stage of determination of a mapping focus is based on the assumption that a mapping focus could be assessed by the mapping system according to junctions in a road map and motion direction of identified slow down towards a junction and/or position of stoppage irregularities, related to a probe position in a road and/or related reports from probes. Such a process would preferably consider the intersection next to the travel position, according to motion direction, to be the departure position from the queue and hence the determination of a mapping focus is enabled. The mapping focus helps to determine one end of the road that could further be mapped by mapping samples. In the third stage mapping samples are constructed.
As mentioned above, when networks such as PLMN or PDN are considered for the implementation of the gathering process there are two options of approach that can be taken. One option is to make some modification to the networks. It is known that modulated messages transmitted simultaneously on the same radio spectrum resources are not interpreted as valid data in PLMN or PDN without sufficient allocation of radio spectrum and transmission time resources, or spectrum for respective spreading code techniques, in order to enable to distinguish between the messages, except for occasional situation when capture effect makes the reception to be valid. Thus in order to be able to accept such simultaneous transmission (which may be expected with the method of using pre-assigned slots for the mapping process) as valid information, without special allocation of radio spectrum resources, when using traditional networks, there is a need to modify these networks. Such modification could be implemented in different ways. For example, the used channel could, at some predetermined times, be modified so that according to a protocol of the network it would be allocated and would be used by the dedicated mapping system, or by a further modification of the detection process in the network it would be enabled to consider the carrier detection as valid information at such times that the channel would be used for gathering process (as further described in FIG. 19). In the latter case one preferred way to implement the communication is to use received signal integrated over time and to compare it to a threshold, to determine if there was a response by probes or not. When TDMA is used with the access to the channel, the slots of this channel can be used for signals transmitted by the probes. For example, a traffic channel on a physical channel used with CCCH in GSM-PLMN (using the same carrier-physical channel) used also for RACH (Random Access Channel) could be allocated in certain predetermined times. Another example could consider a random access channel that enables an access approach, for example, such as Aloha or DSMA, to be used at certain times for the gathering process. Such channels are designed to enable random access of mobile transmitters while considering co-channel interference, e.g., non slotted random access methods such as Aloha and DSMA or slotted access versions of Aloha with or without reservation method. Non slotted random access enabled carrier is less suited than slotted enabled ones to the implementation of the gathering process since with the process suggested as described above, there is a need to synchronize the communication to slots and hence there is a need for further modifications to make it work. When the access to network access channels are controlled by busy indication bits, such as used with DSMA, implemented with CDPD and NA-TDMA, such indication could be used at certain predetermined times to allocate time for the gathering process or to allocate a logical channel. With GSM, for example, a logical channel such as TCH could be allocated for this purpose. Pre-allocated times are required for the access of probes. This would require prior information to be provided to the probes, by control messages that would inform the probes about access timing to the PLMN/PDN. Physical channels that are not designed to enable random access from mobiles are not recommended for this purpose. However, if a channel, not designed to be used for random access transmission is considered for the gathering process, there is a need pay attention to the maximum co-channel interference that could affect other cells, as it is a-priori considered with random access channels. A traffic channel is used for single source data or voice transmission. To use such channels for the gathering process, longer pulses and other methods can be used to improve the detection probability while minimizing transmission power.
A second, alternative, option to implementing the gathering process through PLMN and PDN networks, which does not require modifications to the PLMN/PDN networks, can be considered by giving up on some of the capabilities provided with a system described above. The feature that would be given up provides the rapid search for traffic jams according to the size of congestion together with the ability to make gradual control on the resolution of the mapping. By giving up this feature it would become feasible to use networks such as PLMN and PDN for the gathering process without the need to make modifications to the network, as described in the following. Further give up cost when using this approach will be the need to make some adaptations to the gathering process while considering varying delays in transmission of data from probes to the mapping processor. The logic of the suggested method described above will also hold with this modification. However, since frames/packets of data are used with the transmission in PLMN and PDN of implementation of the second option, predetermined resolution in the data would preferably be considered with the probe updates to the mapping processor. Such messages would be transmitted to the mapping processor through the PLMN and PDN as data that informs about e.g., the position of the sensed traffic required according to predetermined threshold of traffic, rather than transmitting indication in a position related slot. This could be implemented by using global coordinates such as can be achieved with GPS receiver or with road related position when data such as provided with car navigation system is used with each probe. To reduce the load on the network, dynamic threshold conditions would preferably be broadcast to the probes to screen out non required updates about low level of slow downs, as suggested with the queries above. Dynamic thresholds could be set in relation to selective areas and to different levels of traffic to provide more control on the update load according to affordable load on the PLMN and PDN at different times. According to traffic thresholds the probes can use, at any time, medium access channels of PLMN and PDN to initiate updates related to slow downs or stoppages. An update message would preferably include a position to identify the congested road and preferably travel direction and motion rates. In case that an update indicates that most likely a queue should be considered, a first mapping focus, such as expected departure position of the queue, which would be common to probe updates for a mapping sample, could then be estimated by the mapping system. Further to focus determination the mapping system can use broadcast channel to transmit mapping queries to construct mapping samples required by the method described in order to determine parameters of the queue according to mapping samples. The segment of road that corresponds to a mapping sample could be determined with the help of the focus determination for one end of the road segment. The other end of the segment could arbitrarily be determined and possibly consider prestored statistical data of the traffic in the mapped segment. Such segmentation would be necessary to distinguish between different segments, sometimes even in the same road, that would preferably have different mapping timing. Thus segments would preferably be used for determining respective common timing for position reports transmitted by probes for the same mapping sample. Thus mapping samples correspond to segments of road determined by the mapping system according to related characteristics of the mapped road. Mapping sample could be constructed by using, for example, broadcast channel by the mapping system to determine, by control message to the probes, a road segment for mapping samples and sampling time as a first stage. Then, the probes may use a network access channel in order to send to the mapping system their position or their position update in the mapping sample or, if preferred, related position to the mapping focus, according to predetermined procedure. It should be noted that with the approach of this option, the mapping focus is not crucial to be provided to the probes before enabling the gathering process of a mapping sample, so that communication load could be reduced. With this approach, the information provided as data frame/data packets by the probes to the mapping processor has relatively high overhead which makes some additional bits in a message to have small affect (in percentage) on the communication load. In such case the mapping segment and timing of sampling could be provided by the mapping system to the probes to trigger construction of mapping samples and the probes can use position related reports, which would be longer than messages that provide just distance report from a mapping focus. The position related data could just relate to global positioning of the probe or e.g., to a road map related position used with a car navigation system, and the mapping focus would actually be considered by the mapping processor only. The medium access of PLMN/PDN is used asynchronously by many different probes. When probe updates to a mapping sample are considered, there is a need to overcome non correspondence between sequential order of reception times of probe updates and sequential order of probe positions within a mapping sample. With a mapping sample a common reference time is required in relation to position updates to a mapping sample, which should represent a snapshot of positions. In practice the response time for each probe update is expected to be different. Successful transmission of an update depends on the access channel loads and may further be affected by network delays. To resolve these time differences an artificial synchronization can be used by using the technique proposed to map queues, in order to overcome delays in updates to a mapping sample. The technique refers to the capability of the mapping system to determine a reference time for a mapping sample and the capability to transmit such time to the probes as a time reference for required position updates to a mapping sample, as well as the capability of probes to store past positions for such purpose, that could be used to enable a probe to transmit a position update that corresponds to the reference time determined for the mapping sample. This update message should include indication that would enable the mapping processor (part of the mapping system that arranges updated reports from probes to mapping samples and determines the queue length and other parameters of the queue) to identify the relation between the position related updates and the mapping sample. For example, a probe update will include reference to the mapping sampling time of the informed position, either directly, or indirectly by referring for example to a serial number of a mapping sample or to a control message that corresponds with the mapping sample or a combination of such possibilities. This would help the mapping system to arrange informed position related updates according to respective mapping samples in the right order. It would rather be an advantage to get from a probe, automatically, auxiliary information such as motion rate in the queue and planned direction of the travel after passing the exit point of the queue. This information could be determined by the probe according to current position and planned route, for example, if a car navigation system is used, or by sensing the blinking direction lights of the car, otherwise, an image route plan, stored in the mapping system can be used with selective queries. According to special control-message from the mapping system to probes, and in case probes could distinguish between lanes, it would in some cases be an advantage to get lane distinguished position report from probes, in order to be able to map lane related queues. Preferably the auxiliary information, provided by probes, would include estimated time when traffic light changes to green and its time period, or otherwise time and position of the first response to green light could be provided to help the mapping system to perform the estimation. (It should be noted that the sampling time is not very sensitive to an accurate estimation of green light turn on time, since mapping samples are preferably being taken with respect to the time that queues approach a maximum length, in which case there is a delay between the green light turn on time and the time of its actual effect on the most significant sampled segment which is the end of queue). Green light related timing could help to synchronize the probes to transmit time related positions preferably required by the mapping samples so that a farthest probe in a sequence of mapping samples would best reflect the maximum length of the queue, as described elsewhere. This timing could also be used as reference time to construct mapping samples for mapping any intermediate stage, at any point of time between two subsequent times when green light turns on, when the queue is expected to be shorter than its maximum length in a traffic light cycle time. The green light timing could be estimated according to times of transition, (from stop to start), which probes experience in their motion along the queue. Preferably valid start, in this context, would be defined when motion velocity exceeds a defined threshold. The threshold would preferably be defined according to one or more parameters such as minimum velocity, minimum acceleration, duration of maintained average velocity, minimum distance of travel, condition of passage of a certain point e.g. road junction, (as further explained with respect to the use of information about exit point). Another way is to estimate the timing of the traffic lights by the mapping system, based on raw data received from probes. This would require auxiliary information, preferably provided with the probe position report, which would include also position related to the transition time along with time of the transition. Such transitions should consider some threshold, such as minimum motion ahead in the queue in order to make the report more reliable. Probes which are close to the exit may preferably have higher priority for the timing estimation. Another possibility to make the green light timing estimate is to make use of the computation power in the probe vehicles, based on traffic light exit point information. With such an approach, position of the exit point could be provided to the probes, by the mapping system, for example, through the radio network and the probe would make the time estimation to provide it as auxiliary information preferably along with a position report. If the probe processor has an access to a map of traffic light positions, then the probe can determine the position of the traffic lights according to the map. When there is no traffic light involved with a queue the sampling time for mapping samples could be determined arbitrarily and the mapping cycle time would determine the resolution of the length estimate. Mapping cycle time can be specific to a mapping process of a specific road. The departure rate could be used to determine the preferred mapping cycle for a required resolution of length estimate. Higher departure rate requires shorter cycle to preserve resolution of length estimate. The storage of past positioning in the probes could help the mapping system to control the access load of probes and to distribute it over time so that it would prevent bottlenecks in access to the PLMN/PDN, while preserving different required periods of mapping cycles for different roads. For this purpose the report times from the probes are controlled by the mapping system while the reports from the probes would refer to the timing of samples required according to specific cycle and reference time similar to timing used with specific green light. The control messages could even consider whether to allow access or partial access of probes to the network when the load on the network is high. Such messages could be provided along with the triggering messages to start a construction of mapping samples for a certain segment of road, which include sampling timing and road segment for the mapping sample. When an update according to a position, e.g., traffic light controlled road, or according to threshold that most likely informs about a slow down but not on a typical queue e.g., relatively high speed of traffic, then a homogeneous segment of road could be considered for the same traffic level. This could hold for any of the mentioned mapping systems in order to simplify process when accurate mapping of queue might not be required. With the implementation of the second option, (using non modified PLMN/PDN approach), the access of probes to the mapping system through the radio network is different from the one suggested in implementation of the first option, and hence there is a need to consider the way to gather the mapping samples as described above. Once a set of mapping samples is constructed the estimation of the length of the queue is the same for implementation of the second and implementation of the first option and, is performed according to the farthest probe in the set of mapping samples as suggested earlier. As also mentioned, rapid estimation of the length of the queue requires to use pre stored statistics of the average arrival rate of vehicles to the mapped segment of the road and, average arrival rate of probes or otherwise the percentage of probe in the arrivals. Such statistics can be either constructed or refined in real time by using concatenation of non overlapped segments of mapping samples. This may require concatenation with respect to a sufficient number of mapping samples. With the implementation approach of the second option the position resolution is determined by the probe and could follow the resolution of the in vehicle positioning sensors such as GPS, dead reckoning and, even map matching when car navigation is used. The estimated number of vehicles between two positions of probes in the concatenated samples will remain the same as suggested elsewhere in this application and could rely on a predetermined average occupation length of a vehicle. As for the reports from probes it would further be preferred to keep anonymity and to use a single (uniform) identification for probes so that anonymity will be preserved.
A combination of the first and the second option is also possible. For example to implement the search process by using the first option, while using the second option for the implementation of gathering mapping samples.
In accordance with the first option of the method of mapping queues, the process of gathering position related updates from probes, associated with the construction of mapping samples, is being made through a PLMN or a PDN, which allocates radio communication resources to pre-assigned slots, according to a predetermined protocol associated with the PLMN or PDN.
With a further implementation of the first option the PLMN or PDN is equipped with a special unit in a base station that detects received signals in pre-assigned slots and according to a predetermined protocol converts the information associated with the detection to a respective bit stream which is further transmitted to a mapping processor as a data message.
In accordance with the second option of the method of mapping queues, the process of gathering position related updates from probes, associated with the construction of mapping samples, is being made through a PLMN or PDN and wherein the position related updates are data messages transmitted by probes according to a data communication protocol associated with the radio communication medium and wherein a message includes the position related data and auxiliary data that enables to determine time associated with the position related update.
With a further embodiment of the implementation of a mapping system and probes it would be preferred to exploit radio spectrum resources in an efficient way that would save the need to frequently broadcast mapping control messages (queries that trigger probes to respond to a mapping process). This possibility could derive from the characteristic of a queue mapping process which in addition to the requirement to take a minimum number of mapping samples (depending on the percentage of probes in the traffic) a queue would typically require a continuous mapping process to track the queue parameters during a few minutes and sometimes even much more. During this time duration it might be unnecessary to repeat a trigger mapping request, and it would be enough to either allocate communication resources according to predetermined protocol, or in the case of using the non modified PLMN/PDN approach to enable further non solicited updates from probes to the network, according to a predetermined protocol. In order to prevent a situation wherein due to some probes which might have failed to receive an original trigger message and therefore not respond will reduce the effectiveness of the mapping process, it would be preferable according to a predetermined protocol to repeat through a broadcast the trigger message with a cycle time which is longer than the response update cycle time. In case of probe updates that are being provided through pre-assigned slots it would be preferable to use such communication resources dynamically for different roads at different times. In such a case a trigger message may change the allocation of pre-assigned slots from one road to another, and as a result a probe with a position relevant to the previous road and which might have failed to receive such a message might interfere and violate the update to the new mapped road. In order to prevent such possible violation it would be preferable to repeatedly broadcast, in a short cycle, according to predetermined protocol short messages that notify about changes of allocation of specific pre-assigned slots, preferably the latest ones.
In a further embodiment of the invention, it would be sometimes preferable to predict the number of probes that plan to arrive at a given road, which is being mapped by the mapping system, within a certain forward period of time, e.g. the next time interval between two successive or non successive mapping samples. Such a prediction could be made in a short duration of time and would help to determine more quickly the local percentage of probes in relation to the total number of vehicles arriving to a mapped queue within a given time period. As a result a more accurate determination can be made, from the initial stages of a mapping process of a certain queue, of the time period in which a number of mapping samples are to be gathered according to required accuracy level of the length, for estimating the average length of a mapped queue. This would actually reduce the response time of the system which would possibly enable to obtain a more accurate mapping of length of queues. This is due to the assessment of probe percentage being predicted and made available to the mapping system at the initial stages of mapping rather than as result of information accumulated in the course of the mapping and enable to eliminate the need for a data base of off line statistics. When very few probes (e.g. 2%-5% of the vehicles) are expected to arrive to the mapped queue, usually as a result of the low percentage of probes relative to the overall number of vehicles arriving to a certain mapped road at a certain time, it might take a relatively long time before an acceptable estimate of percentage of probes could be derived out of concatenation of non overlapping mapping samples. In order to reduce the time, a counting method with respect to transmissions of probes in pre-allocated slots, selected by the probes according to a distribution criterion that exists among them or according to an artificial one, could be used by the mapping system to evaluate the number of probes planning to arrive to a queue in a forward time interval. With this counting process and according to a predetermined protocol probes that plan to arrive in a predetermined forward time interval will transmit a signal in one of a plurality of pre allocated slots, specially allocated by the mapping system for such transmissions. When a natural distribution is used by a probe as a criterion for the selection of a slot to a signal transmission, the allocated slots could be assigned according to time intervals of arrival to the mapped queue or according to distance from the queue or a combination of these criteria. When an artificial distribution is considered a random process can be used by the probe to select a slot for the signal transmission. Any possible combination between selection criteria could be used to increase the confidence in the process. The proportion between the number of slots that were used by probe transmissions and the number of pre-allocated slots could be used to determine the number of probe transmissions. Preferably the number and the individual assignment of the various allocated slots would a-priori enable to discriminate with high probability between the transmitted signals in different slots in order to evaluate with high confidence the number of such probe transmissions by counting the number of slots in which there was a response. This counted number when put in proportion to an estimated number of the vehicles expected to arrive in this forward time interval could provide an estimate of the relative percentage of probes in the forward time interval with respect to the queue being mapped. This method can be used in a combination with a conventional method to estimate the percentage of probes when a few or more non overlapping mapping samples are becoming available and hence could be concatenated in order to be used as a sample for estimating the percentage of probes according to e.g., parameter estimation of a probability distribution function as described with another embodiment. For example if the time interval is statistically long enough the arrived probes in the mapping samples can be used in proportion to the number of the arrived vehicles to provide the percentage of probes according to Maximum Likelihood Estimate of a Binomial parameter counted number, for the elapsed time interval, and the counted number according to the counting process could be used in the same way for the forward time interval, and hence a combination of these two estimates can be used e.g., using maximum likelihood combining estimate. According to a predetermined protocol a number of such counts could be summed in order to evaluate the percentage of probes according to longer time intervals, or relatively long time intervals could be used with each counting process. In this respect the allocation of slots in a mapping process could include in addition to pre-assigned slots for gathering a mapping sample a number of auxiliary slots for the counting process, either allocated according to a predetermined protocol with each mapping sample or with respect to a group of mapping samples. The number of the auxiliary slots for the counting process should preferably consider an acceptable limit for expected probes in the forward time interval preferably determined according to the arrival distribution.